1. Field of the Invention
This invention relates to resource allocation and, more particularly, to allocating a constrained common resource among a plurality of demands for the resource.
2. Description of the Prior Art
The term "resource allocation" problem applies to that class of problems, which has as a common characteristic the need to physically allocate a restricted or constrained common resource among a plurality of demands for the resource. The term "cutting stock" problem relates to a kind of resource allocation problem, which is usually found in a manufacturing or transportation environment, where the common resource and the demands for the resource have geometric meaning or interpretation. For example, the article by R. W. Haessler entitled "Selection and Design of Heuristic Procedures for Solving Roll Trim Problems," Journal of the Institute of Management Sciences, Vol. 34, No. 12 (December 1988), pp 1460-1471 discloses a cutting stock problem that relates to a paper mill, which produces large rolls of paper, and specifically to a heuristic procedure for solving one-dimensional roll trimming, or cutting, or slicing a large width roll or rolls of paper into a plurality of smaller width rolls of paper. The pragmatic significance of the heuristic procedure is keyed to the fact that it is common in the paper mill industry to cut a large width roll or rolls into a plurality of smaller width rolls of paper. Relating the resource allocation problem and the cutting stock problem to the paper mill example, it may be noted that the large roll corresponds to a constrained common resource while the smaller rolls correspond to a plurality of demands for the resource.
In the process of cutting a large roll of paper, there is usually a large number of alternative settings for the knives which are used to cut the large roll into the plurality of smaller rolls. Ideally, it is desired that the knives be set and, perhaps, reset several times in such a way that the large roll would be cut into a plurality of smaller rolls without leaving any waste. Unfortunately, the ideal setting of the knives is seldom achieved for at least two reasons. One, the sum of the widths of the smaller rolls may not equal the width of the large roll. Second, even if the sum of the widths of the smaller rolls does equal the width of the large roll, the number of alternative settings for the knives may be so large that the time to find the ideal setting may be prohibitively long and, hence, is likely to be cost ineffective.
In light of the above, it is common to settle on a solution which may have some waste but which balances waste against the time to find a recommended setting of the knives. Notwithstanding, known processes to find a recommended solution of the allocation of the constrained common resource to meet the plurality of demands still require excessive amounts of time and, therefore, a more timely solution remains needed in the industry.